package graph.algorithm;

import graph.Edge;
import graph.Graph;
import graph.Node;

import java.util.ArrayList;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RegionFinder {
    private Graph<?, ?> graph;

    public RegionFinder(Graph<?, ?> graph) {
        this.graph = graph;
    }
    public Set<List<Node<?>>> findRegions() {

        HashSet<Edge<?, ?>> forwardSet = new HashSet<Edge<?,?>>();
        HashSet<Edge<?, ?>> backwardSet = new HashSet<Edge<?,?>>();
        Set<List<Node<?>>> result = new HashSet<List<Node<?>>>();
        for (Edge<?, ?> edge : graph.getEdges()) {
            process(edge, forwardSet, backwardSet, result);
        }
        return result;
    }

    private void process(Edge<?, ?> edge, HashSet<Edge<?, ?>> forwardSet,
            HashSet<Edge<?, ?>> backwardSet, Set<List<Node<?>>> result) {
        if (!forwardSet.contains(edge)) {
            forwardSet.add(edge);
            List<Node<?>> loop = getRegion(edge.a, edge.b, forwardSet, backwardSet);
            result.add(loop);
        }
        if (!backwardSet.contains(edge)) {
            backwardSet.add(edge);
            List<Node<?>> loop = getRegion(edge.b, edge.a, forwardSet, backwardSet);
            result.add(loop);
        }
    }

    private List<Node<?>> getRegion(Node<?> a, Node<?> b,
            HashSet<Edge<?, ?>> forwardSet, HashSet<Edge<?, ?>> backwardSet) {
        ArrayList<Node<?>> result = new ArrayList<Node<?>>();
        double minAngle = 2*Math.PI;
        for (Edge<?,?> e : graph.getEdges(b)) {
            if (e.a == a || e.b == a) continue;
            double angle = angle(a, b, e.opposite(b));
           
        }
        return result;
    }
    private double angle(Node<?> a, Node<?> b, Node<?> c) {
        double dx1 = a.pos.x-b.pos.x;
        double dy1 = a.pos.y-b.pos.y;
        double dx2 = c.pos.x-b.pos.x;
        double dy2 = c.pos.y-b.pos.y;
        double a1 = Math.atan2(dy1, dx1);
        double a2 = Math.atan2(dy2, dx2);
        double angle = a2-a1;
        if (angle < 0) angle += 2*Math.PI;
        return angle;
    }

}